package sword.offer;

import java.util.Arrays;

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Forty {
    /**
     * 利用快排的思想
     * 当一轮快排结束时，i落在下标为k 或者 k-1时，那么该数组的前k位数就是最小的。
     * */
    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            quickSort(arr, k, 0, arr.length-1);
            return Arrays.copyOf(arr, k);
        }

        void quickSort(int[] arr, int k, int l, int r){
            // 排序部分 的起点>=k 或者终点 <= k就不用参与排序了
            if(l >= r || l > k || r < k) return;
            int i = l;
            int j = r;
            int temp = 0;
            while(i < j){
                while(i < j && arr[j] > arr[l]){j--;}
                while(i < j && arr[i] < arr[l]){i++;}
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            arr[i] = arr[l];
            arr[l] = temp;
            quickSort(arr, k, l, i-1);
            quickSort(arr, k, i+1, r);
        }
    }
}
